package com.szymon.computational;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.logging.Logger;

/**
 * Calculating minimum value paths down a tree summing elements
 * @author szymon.wartak
 *
 */
public class MinTrianglePath {

	/**
	 * @param args Triangle path input from system in
	 */
	public static void main(String[] args) {

		MinTrianglePath tree = new MinTrianglePath();
		try {
			//tree.inputTree(new BufferedReader(new FileReader("/home/szymon/dev/TrianglePaths/resources/triangle.txt")));
			tree.inputTree();
		    tree.outputTree();
		    System.out.println("min path value = "+tree.minPathValue());
		} catch (Exception e) {
			e.printStackTrace();
		}

	}
	
	Logger log = Logger.getLogger(getClass().getName());
	private ArrayList<Node> leaves;
	
	public MinTrianglePath() {}
	
	/**
	 * Default tree input method is to read from console input
	 */
	public void inputTree() { inputTree( new BufferedReader(new InputStreamReader(System.in))); }
	public void inputTree(BufferedReader br) {
		String line = null;
	    try {
	    	while(true) {
		    	line = br.readLine();
		    	if(line.trim().equals("EOF"))
		    		break;
		    	addLayer(line.split(" "));
	    	}
	    	
	    } catch (IOException ioe) {
	    	log.severe("error with line: "+line);
	    	ioe.printStackTrace();
	    }
	}
	
	public void outputTree() {
		log.info("Outputting tree...");
		ArrayList<Node> currentList = leaves, nextList;
		while(currentList.size() > 0) {
			nextList = new ArrayList<Node>(leaves.size()-1);
			for(int i1=0;i1<currentList.size();i1++) {
				System.out.print(currentList.get(i1).getValue()+"("+currentList.get(i1).getMinPathValue()+") ");
				if(currentList.get(i1).getLeftParent() != null) {
					nextList.add(currentList.get(i1).getLeftParent());
				}
			}
			currentList = nextList;
			System.out.println();
		}
	}
	
	/**
	 * Adding rows to the tree. Currently handles only adding from root (size 1) to leaves
	 * @param row An array of values for the next row
	 */
	public void addLayer(String[] row) {
		log.fine("Adding layer of length "+row.length+". Previous length is "+
				(leaves == null ? 0 : leaves.size()));
		if(leaves == null) {
			if(row.length == 1) {
				leaves = new ArrayList<Node>(Arrays.asList(new Node[]{
					new Node(null, null, Integer.valueOf(row[0].trim()))
				}));
			}
		} else if(row.length == leaves.size()+1) {
			ArrayList<Node> newLeaves = new ArrayList<Node>(leaves.size()+1);
			for(int i1=0; i1<row.length; i1++) {
				if(i1 == 0) {
					newLeaves.add(new Node(null, leaves.get(i1), Integer.valueOf(row[i1].trim())));
				} else if(i1 == leaves.size()) {
						newLeaves.add(new Node(leaves.get(i1-1), null, Integer.valueOf(row[i1].trim())));
				} else {
					newLeaves.add(new Node(leaves.get(i1-1), leaves.get(i1), Integer.valueOf(row[i1].trim())));
				}
			}
			leaves = newLeaves;
		} else {
			log.severe("Wrong number of number in row: "+(leaves.size()+1));
		}
	}

	/**
	 * @return the min path value for the tree from the current set of leaves
	 */
	public Integer minPathValue() {
		Integer min = 999999999;
		for(Node n : leaves) {
			if(n.getMinPathValue() < min)
				min = n.getMinPathValue();
		}
		return min;
	}

}

class Node {
	Node leftParent, rightParent;
	Integer value, minPathValue;
	
	public Node(Node leftParent, Node rightParent, Integer value) {
		this.leftParent = leftParent; 
		this.rightParent = rightParent;
		this.value = value;
		calcMinPathValue();
	}

	private void calcMinPathValue() {
		if(leftParent == null && rightParent == null)
			minPathValue = value;
		else if(leftParent == null) 
			minPathValue = value + rightParent.getMinPathValue();
		else if (rightParent == null)
			minPathValue = value + leftParent.getMinPathValue();
		else
			minPathValue = value + Math.min(leftParent.getMinPathValue(), rightParent.getMinPathValue());
		
	}
	public Integer getValue() { return value; }
	public Integer getMinPathValue() { return minPathValue; }
	public Node getLeftParent() { return leftParent; }
}
